package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/number-of-unequal-triplets-in-array/'>数组中不等三元组的数目(Number of Unequal Triplets in Array)</a>
 * <p>
 * 给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目：
 *     <ul>
 *         <li>0 <= i < j < k < nums.length</li>
 *         <li>nums[i]、nums[j] 和 nums[k] 两两不同 。换句话说：nums[i] != nums[j]、nums[i] != nums[k] 且 nums[j] != nums[k] 。</li>
 *     </ul>
 *     返回满足上述条件三元组的数目。
 * </p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [4,4,2,4,3]
 *      输出：3
 *      解释：下面列出的三元组均满足题目条件：
 *          - (0, 2, 4) 因为 4 != 2 != 3
 *          - (1, 2, 4) 因为 4 != 2 != 3
 *          - (2, 3, 4) 因为 2 != 4 != 3
 *          共计 3 个三元组，返回 3 。
 *          注意 (2, 0, 4) 不是有效的三元组，因为 2 > 0 。
 *
 * 示例 2：
 *      输入：nums = [1,1,1,1,1]
 *      输出：0
 *      解释：不存在满足条件的三元组，所以返回 0 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>3 <= nums.length <= 100</li>
 *      <li>1 <= nums[i] <= 1000</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/23 16:14
 */
public class LC2475NumberOfUnequalTripletsInArray_S {

    static class Solution {
        public int unequalTriplets(int[] nums) {
            int triplets = 0;
            Map<Integer, Integer> counts = new HashMap<>();
            for (int num : nums) {
                counts.put(num, counts.getOrDefault(num, 0) + 1);
            }
            int n = nums.length;
            int prevCount = 0;
            Set<Map.Entry<Integer, Integer>> entries = counts.entrySet();
            for (Map.Entry<Integer, Integer> entry : entries) {
                int currCount = entry.getValue();
                triplets += prevCount * currCount * (n - prevCount - currCount);
                prevCount += currCount;
            }
            return triplets;
        }
    }
}
